package com.linzm.leetcode.primary.exercises2_20230116;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author zimingl
 * @Date 2023/1/21 19:15
 * @Description: 只出现一次的数字
 */
public class Demo16_136 {
    /**
     * 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     * 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
     */
    public static void main(String[] args) {
        Demo16_136 demo16_136 = new Demo16_136();
//        int[] nums = {2, 2, 1};
        int[] nums = {4, 4, 1, 1, 2};
        int num = demo16_136.singleNumber3(nums);
        System.out.println(num);
    }

    private int singleNumber(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        Arrays.sort(nums);
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if (stack.isEmpty()) {
                stack.push(nums[i]);
                continue;
            }
            if (stack.peek() != nums[i]) {
                return stack.peek();
            } else {
                stack.pop();
            }
        }
        return stack.peek();
    }

    private int singleNumber2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        Arrays.sort(nums);
        int left = 0;
        for (int i = 1; i < nums.length; i += 2) {
            if (nums[left] != nums[i]) {
                return nums[left];
            } else {
                left += 2;
            }
        }
        return nums[left];
    }

    private int singleNumber3(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int count = map.getOrDefault(nums[i], 0) + 1;
            map.put(nums[i], count);
        }
        Integer[] integers = map.entrySet().stream().filter(entry -> entry.getValue() == 1).map(entry -> entry.getKey()).toArray(Integer[]::new);
        Map<Integer, Integer> collect = map.entrySet().stream().filter(entry -> entry.getValue() == 1).collect(Collectors.toMap(x -> x.getKey(), x -> x.getValue()));
        return integers[0];
    }
}

